//
//  StackAndQueue.swift
//  ArithmeticWithSwift
//
//  Created by 神州锐达 on 2018/9/26.
//  Copyright © 2018年 onePiece. All rights reserved.
//

import Foundation


//栈和队列
//栈:先进后出(First In Last Out)的结构,又叫FILO
//队列:先进先出(First In First Out)的结构,又叫FIFO

//MARK:- 栈
protocol Stack {
    //associatedtype:关联类型 相当于范型 在调用的时候可以根据associatedtype指定的Element来设置类型
    associatedtype Element
    
    //    判断栈是否为空
    var isEmpty: Bool {get}
    //    栈的大小
    var size: Int {get}
    //    栈顶元素
    var peek: Element? {get}
    
    //    进栈
    mutating func push(_ newElement: Element)
    //    出栈
    mutating func pop() -> Element?
}

//一个整形数栈
//注解:利用协议申明了栈的属性和方法,并在结构体中声明数组stack,对数组数据进行append和poplLast操作,完成入栈出栈操作,比较简单.
struct IntegerStack: Stack {
    
    //typealias:类型别名 指定协议关联类型的具体类型 和associatedtype成对出现的
    typealias Element = Int
    
    //    Int数组
    private var stack = [Element]()
    
    var isEmpty: Bool {return stack.isEmpty}
    
    var size: Int {return stack.count}
    
    var peek: Int? {return stack.last}
    
    mutating func push(_ newElement: Int) {
        return stack.append(newElement)
    }
    
    mutating func pop() -> Element? {
        return stack.popLast()
    }
    
    
}


//MARK:- 队列
protocol Queue {
    
    associatedtype Element
    //队列是否为空
    var isEmpty: Bool {get}
    //队列大小
    var size: Int {get}
    //队列首元素
    var peek: Element? {get}
    //入列
    mutating func enqueue(_ newElement: Element)
    //出列
    mutating func dequeue() -> Element?
    
}

struct IntegerQueue: Queue {
    
    typealias Element = Int
    
    //声明左右2个数组
    private var left = [Element]()
    private var right = [Element]()
    
    var isEmpty: Bool {return left.isEmpty && right.isEmpty}
    var size: Int {return left.count + right.count}
    var peek: Element? {return left.isEmpty ? right.first : left.last}
    
    //在right数组中添加新元素
    mutating func enqueue(_ newElement: Int) {
        right.append(newElement)
    }
    
    //出队列时 首先判断left是否为空
    mutating func dequeue() -> Int? {
        if !left.isEmpty {
            //reversed: 倒序遍历数组
            left = right.reversed()
            //删除right数组
            right.removeAll()
        }
        //删除left数组的最后一个元素
        return left.popLast()
    }
}

